Group elevator scheduling (GES) is a combinatorial optimization problem for a bank of two or more elevators. The most common instance of this problem deals with assigning elevator cars to passengers requesting an elevator car by means of an UP or DOWN button. In response to receiving the requests, a scheduler assign a car to each passenger so that a performance metric, for example an average waiting time (AWT) for all passengers, is minimized. The AWT is defined as a time interval from the moment a passenger makes the request until a car arrives, averaged over many requests. A large number of scheduling methods are known. However, there are significant obstacles to achieving an optimal AWT.
The first obstacle is the combinatorial complexity of the scheduling problem. If a building has an elevator bank with C cars and N passengers must be assigned to the cars, then there are CN possible assignments, each resulting in a different AWT. Even for a small number of cars and passengers, determining an optimal assignment by an exhaustive search of all CN assignments is not feasible, particularly given the relative short response times required. For this reason, multiple heuristic and approximate methods have been developed, see Nikovski U.S. Pat. No. 7,546,905, “System and method for scheduling elevator cars using pairwise delay minimization,” U.S. Pat. No. 7,484,597, “System and method for scheduling elevator cars using branch-and-bound,” U.S. Pat. No. 7,014,015, “Method and system for scheduling cars in elevator systems considering existing and future passengers, and U.S. 20030221915, “Method and system for controlling an elevator system.” In U.S. Pat. No. 7,014,015, Nikovski describes a scheduling method where future requests are predicted at the main floor, and the waiting times for such future requests are included in the decision process. A shortcoming of that method is that only future requests at the main floor are considered.
The second obstacle to minimizing the AWT is due to incomplete, untimely and inaccurate information. For example, most hall call requests do not include a destination floor, but only an UP or DOWN direction. Typically, the destination floor is only indicated after the passenger enters the car. One approach of dealing with this problem is to assume a particular destination, for example, the last floor in the requested direction. A different approach determines the AWT for all possible destinations using a method to reduce the AWT with respect to arbitrarily selecting a single destination floor, see Nikovski et al., “Method and system for controlling an elevator system, U.S. Pat. No. 6,672,431. However, that method still cannot compensate for the lack of precise information. More advanced signaling mechanisms have been considered, including direct specification of the destination floor by means of an input panel outside the elevator for Destination Control (DC) scheduling. As a significant disadvantage, this increases the cost of the system, and is typically only used at the main floor, if at all.
A third obstacle is the inability to predict future requests and destinations. Typically, the scheduler can only service known requests and destinations. As a result, most schedulers use an empty-the-system algorithm (ESA), see Bao et al., “Elevator dispatchers for down-peak traffic,” Technical report, University of Massachusetts, 1999. In ESA schedulers, all future passenger arrivals are ignored, which is an obvious inaccuracy with respect to what will actually happen to the elevator system. A major problem with the ESA is its inability to predict future requests. In effect, the ESA makes a schedule that can result in all cars being positioned in only one small part of the building, leaving large parts uncovered. The reason for this is that all terminal positions of the cars are considered equally good, as long as no passengers are waiting so there is no reason to prefer one position over another.
Conventional GES systems typically deal with the lack of information and limited computing resources by simplifying the optimization problem. Several simplification can be used.
In one method, mutual delays due to the assignment of two or more passengers h to the same car are ignored. The selected car is c*=argmincWc(h|Ø), where Wc is a function that expresses the waiting time of one or more passengers given that another set of zero or more passengers are also assigned to the same car, and Ø is the null set. This simplification reduces the scheduling problem to selecting the car that minimizes the waiting time W for passenger h, regardless of whether other passengers have been or will be assigned to the same car. That method ignores the delays that existing passengers assigned to the same car would cause to the current passenger, as well as the delays the current passenger making the request and to be scheduled would cause to the existing passengers.
The most common scheduling method used in conventional GES systems accounts for interdependence of assigned passengers, but ignores future passengers. That method determines the best possible assignment for passengers that have requested service, but have not boarded a car yet. Because AWT minimization reduces to finding an assignment that would load the existing passengers into cars as fast as possible, this kind of methods are also known as empty-the-system-methods (ESA). Let H(t) represent the set of passengers who have arrived by time t, but have not been served yet and are still waiting. Then, the goal is to find assignments for the passengers in H(t) that minimizes their cumulative waiting time W (H(t)) .
In an immediate assignment mode, the assignment for the current passenger h is made immediately and never reconsidered. In this mode, it is sufficient to determine a marginal waiting timeΔWc(h)≐Wc(h∪Hc(t)|h∪Hc(t))−Wc(Hc(t)|Hc(t))for each car c, and assign h to the car with the shortest marginal waiting time ΔWc(h). That is, the scheduler tentatively assigns the passenger h to each car in turn, and selects the car that marginally increases the waiting time. The marginal increase in the waiting time can be written asΔWc(h)=Wc(h|Hc(t))+Σg∈Hc(t)[Wc(g|Hc(t)∪h)−Wc(g|Hc(t))],where g ranges over all passengers in the set Hc.
The first term in the marginal increase is the time needed to serve the passenger h with car c. It also accounts for stops that car has to make due to other passengers in the set Hc(t) already assigned to car c. The remaining terms in the sum account for the increase in waiting time passenger h causes to the passengers already in the set Hc(t), when also assigned to c.
In a reassignment mode, any passenger's assignment could be reassigned at any time when new information is received, including, but not limited to, new arrivals. Effectively, the total waiting times W(H(t)) for every possible assignment is predetermined, but for the passengers in the set H(t), ignoring past and future passengers. Although the resulting set is much smaller than the set H, an exhaustive search is still rarely feasible.
Some methods consider future arrivals at the main floor. Even this limited consideration of future arrivals can result in considerable reduction of the AWT during, for example, a peak up traffic time in the morning, see U.S. Pat. No. 7,014,015, “Method and system for scheduling cars in elevator systems considering existing and future passengers.” As a limitation, that method only considers future arrivals at a single (main) arrival floor, such as a building lobby.
Another practically beneficial method for consideration of future arrivals is described by Suzuki et al. in U.S. 20130186713. An elevator system parks empty cars at floors having a high frequency of use. The system includes a remote call device to perform a hall call registration at a distance from the elevator. The time for moving the elevator car from the parking floor is compared with the walking time to elevator. A determination is made whether or not to perform a standby operation based on the result of the comparison of the times.
Suzuki et al., “Elevator supervisory control system with cars cooperative method,” Proceedings of the ELEVCON'06 World Elevator Congress, pp. 338-346, 1206, simulate an imaginary additional request at each floor for each real request, and the best schedule that can handle both real and imaginary requests, even for a most unfavorable floor for the imaginary request, is selected. While that method significantly improves over the ESA methods, the method still considers only one future request, and the time of the imaginary and actual requests are coincident.
In U.S. Pat. No. 8,220,591, Attala et al. describe a scheduling method for a group of elevators using advance traffic information. The advance traffic information is used to define a “snapshot” problem to improve performance for passengers. To solve the snapshot problem, an objective function is transformed to facilitate the decomposition of the problem into individual car subproblems. The subproblems are independently solved using a two-level formulation, with passenger to car assignment at a higher level, and the dispatching of individual cars at a low level. The primary disadvantage of that method is that future arrivals are assumed to occur with complete certainty, e.g., requests are made on a keypad located at a distance from the elevators, cameras or other sensors in corridors leading to the elevators detest approaching passengers, identification card readers or a hotel conference schedule system supply arrival information at an increased costs. However, complete certainty still cannot be reasonably expected in an actual practical system.
It is desired to provide an optimal scheduling strategy for group elevator systems that takes advance information about uncertain future passenger arrivals into consideration.